//题目:
// 爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
// 最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：
// 选出任一 x，满足 0 < x < n 且 n % x == 0 。
// 用 n - x 替换黑板上的数字 n 。
// 如果玩家无法执行这些操作，就会输掉游戏。
// 只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。

// 示例 1：
// 输入：n = 2
// 输出：true
// 解释：爱丽丝选择 1，鲍勃无法进行操作。

// 示例 2：
// 输入：n = 3
// 输出：false
// 解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    bool divisorGame(int n) 
    {
        //1.创建dp表————dp[i]表示:从数字i开始，爱丽丝先手的情况下，她能否取得胜利
        vector<int> dp(n+1);
        //2.初始化————暂无
        //3.填表————动态转移方程：dp[i]=for(int j=1;j<i;j++) if(i%j==0 && dp[i-j]==false) dp[i]=true
        for(int i=2;i<=n;i++)
        {
            //寻找i的所有因数
            for(int j=1;j<i;j++)
            {
                if(i%j==0 && dp[i-j]==false) 
                {
                    dp[i]=true;
                    break;
                }
            }
        } 
        //4.确定返回值
        return dp[n];
    }
};